limit = 500
is_prime = [True] * (limit + 1)
euler = [0] * (limit + 1)

euler[1] = 1
primes = []
for i in range(2, limit + 1):
    if is_prime[i]:
        primes.append(i)
        euler[i] = i - 1
    for prime in primes:
        if prime * i > limit: break
        is_prime[prime * i] = False
        # 根据i是否与pi互质进行筛选
        euler[prime * i] = euler[prime] * euler[i]
        if i % prime == 0:
            euler[prime * i] = prime * euler[i]
            break

print(euler)
